1. Field of the Invention
The present invention relates to a processor for performing out-of-order execution by using a re-order buffer or the like and to a re-order buffer managing method that can efficiently use the re-order buffer.
2. Description of the Related Art
A system of executing instructions in parallel while skipping over the order of the instructions in a program is called “out-of-order execution”, and it can enhance the practical parallel degree more than “in-order execution”. Therefore, this system is indispensable to high-performance processors.
In an out-of-order execution processor, data dependence relationships such as inverse-dependence and output-dependence are detected, and these are solved to perform the out-of-order execution. The inverse-dependence occurs when a destination register of a subsequent instruction is coincident with a source register of a precedent instruction. The output-dependence occurs when the destination register is coincident between the subsequent instruction and the preceding instruction. These can be solved by holding the execution result of the subsequent instruction in a temporary register and writing data in an original register according to a program order. The execution of an instruction using the execution result of the subsequent instruction can be started by reading out data from the temporary register even before the data are stored in the original register. This is called “registry naming”, and a temporary register used therefor is called a “remaining register”.
In the out-of-order execution processor, a buffer for holding execution start (issue) waiting instructions such as a skipped instruction is called a “reservation station”, and a buffer for carrying out the rewriting of the execution result in program order is called a “re-order buffer ”. As the size of the buffer is large, the range of an instruction string for which the out-of-order execution can be performed can be increased. Further, with respect to the control dependence, a branch destination is predicted and instruction execution is speculatively performed, whereby the parallel execution is enabled. The cancellation of the speculative execution and processing when an exception occurs are generally implemented as a function of the re-order buffer.
As described above, in order to increase the range of the instruction string for which the out-of-order execution can be performed, a re-order buffer having a large size is needed. A technological restriction is imposed on the upper limit of the size, and thus it is important how efficiently the re-order buffer having the restricted size is used. However, there has been hitherto such a disadvantage that even when an speculative instruction string in a re-order buffer is cancelled because of a failure of a branch prediction, an entry used for a non-completed load instruction which is contained in entries used for the speculative instruction string thus cancelled, cannot be immediately used for a subsequent instruction.